#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>

#define REP(i, a, n) for(int i=a;i<=n;++i)
#define PER(i, a, n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
const int SS = N - 4, TT = N - 3, S = N - 2, T = N - 1;
int n, h[N];

struct edge {
    int to, w, next;

    edge(int to = 0, int w = 0, int next = 0) : to(to), w(w), next(next) {}
} e[N];

int head[N], dep[N], vis[N], cur[N], cnt = 1;
queue<int> Q;

int bfs(int s, int t) {
    REP(i, 1, n) dep[i] = INF, vis[i] = 0, cur[i] = head[i];
    REP(i, SS, T) dep[i] = INF, vis[i] = 0, cur[i] = head[i];
    dep[s] = 0, Q.push(s);
    while (Q.size()) {
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            if ( dep[e[i].to] > dep[u] + 1 && e[i].w ) {
                dep[e[i].to] = dep[u] + 1;
                Q.push(e[i].to);
            }
        }
    }
    return dep[t] != INF;
}

int dfs(int x, int w, int t) {
    if ( x == t ) return w;
    int used = 0;
    for (int i = cur[x]; i; i = e[i].next) {
        cur[x] = i;
        if ( dep[e[i].to] == dep[x] + 1 && e[i].w ) {
            int f = dfs(e[i].to, min(w - used, e[i].w), t);
            if ( f ) used += f, e[i].w -= f, e[i ^ 1].w += f;
            if ( used == w ) break;
        }
    }
    return used;
}

int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) ans += dfs(s, INF, t);
    return ans;
}

void add(int u, int v, int w) {
    e[++cnt] = edge(v, w, head[u]);
    head[u] = cnt;
    e[++cnt] = edge(u, 0, head[v]);
    head[v] = cnt;
}

int main() {
    int t;
    scanf("%d", &t);
    REP(cas, 1, t) {
        scanf("%d", &n);
        cnt = 1;
        REP(i, 1, n) head[i] = 0;
        REP(i, SS, T) head[i] = 0;
        add(TT, SS, INF);
        int sum = 0;
        REP(i, 1, n) {
            int f, c, g;
            scanf("%d%d%d", &f, &c, &g);
            h[i] = h[f] ^ 1;
            if ( g ) sum += c;
            if ( h[i] & 1 ) {
                if ( g ) add(S, i, c), add(SS, T, c);
                else add(SS, i, c);
                if ( f ) add(i, f, INF);
            } else {
                if ( g ) add(i, T, c), add(S, TT, c);
                else add(i, TT, c);
                if ( f ) add(f, i, INF);
            }
        }
        if ( dinic(S, T) != sum ) {
            printf("Case %d: -1\n", cas);
        } else {
            printf("Case %d: %d\n", cas, 2 * dinic(SS, TT));
        }
    }
}